package doublePtr

/*
时间复杂度：O（N）
空间复杂度：O（N）
双指针
*/
func reverseOnlyLetters(s string) string {
	i, j := 0, len(s)-1
	bs := []byte(s)
	for i < j {
		if !isAlpha(bs[i]) {
			i++
		} else if !isAlpha(bs[j]) {
			j--
		} else {
			bs[i], bs[j] = bs[j], bs[i]
			i++
			j--
		}
	}
	return string(bs)
}

func isAlpha(b byte) bool {
	if (b >= 65 && b <= 90) || (b >= 97 && b <= 122) {
		return true
	}
	return false
}

/*
时间复杂度：O（N）
空间复杂度：O（N）
栈-先将s的所有是字母的字符压入栈中，然后遍历s，如果遍历到的字符为字母，则从栈中弹出字符，即实现字母全逆序，非字母不变的功能
*/
func reverseOnlyLetters1(s string) string {
	stack := make([]byte, 0)
	for i, _ := range s {
		if isAlpha(s[i]) {
			stack = append(stack, s[i])
		}
	}

	ans := make([]byte, 0)
	for i, _ := range s {
		if isAlpha(s[i]) {
			ans = append(ans, stack[len(stack)-1])
			stack = stack[:len(stack)-1]
		} else {
			ans = append(ans, s[i])
		}
	}
	return string(ans)
}
